//
//  sort.hpp
//  DataStructure
//
//  Created by 劢克科技 on 2020/8/11.
//  Copyright © 2020 Shuleiming. All rights reserved.
//

#ifndef sort_hpp
#define sort_hpp

#include <stdio.h>
#include <stdlib.h>

// 排序算法的稳定性

// *** 插入排序 ***
// 向后移动～
// 适用于有序或者基本有序的数列，倒序数列为最差情况
// 空间复杂度：O(1)
// 时间复杂度：O(n) ~ O(n^2)
// 稳定
void InsertSort(int a[], int len)
{
    int temp, j;
    for (int i = 1; i < len; i++) {
        temp = a[i];
        for (j = i - 1; a[j] > temp && j >= 0; j--) {
            a[j + 1] = a[j];
        }
        a[j + 1] = temp;
    }
}

// *** 希尔排序 ***
// 局部有序 -> 整体有序，多次插入排序
// 增量d1 = n/2, d2 = d1/2 ...直到d=1
// 每一趟，对相距距离为d的元素进行插入排序
// 不稳定，只能基于顺序表
void ShellSort(int arr[], int len)
{
    int i, j, d, temp;

    for (d = len / 2; d >= 1; d /= 2) {
        for (i = d; i < len; i++) {
            if (arr[i] < arr[i - d]) {
                temp = arr[i];
                for (j = i - d; arr[j] > temp && j >= 0; j-=d) {
                    arr[j + d] = arr[j];
                }
                arr[j + d] = temp;
            }
        }
    }
}

// *** 冒泡排序、升序 ***
// 大部分有序最好，逆序最差
// 时间复杂度：O(n) ~ O(n^2)
// 稳定，适用于链表和顺序表
void BubbleSort(int arr[], int len)
{
    for (int i = 0; i < len - 1; i++) {
        int flag = 1;
        for (int j = len - 1; j > i; j--) {
            if (arr[j] < arr[j - 1]) {
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                flag = 0;
            }
        }
        if (flag) {
            break;
        }
    }
}

// ***** 快速排序 *****
// 通过不断地“划分”进行排序
// 时间复杂度：O(n*递归栈) O(nlog2n) ~ O(n^2)
// 空间复杂度：O(nlog2n)递归层数:可以转为二叉树
// 不稳定
int Partition(int arr[], int low, int high)
{
    int pivot = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= pivot) {
            high--;
        }
        arr[low] = arr[high];
        while (low < high && arr[low] <= pivot) {
            low++;
        }
        arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
}

void QuickSort(int arr[], int low, int high)
{
    if (low < high) {
        int pivotpos = Partition(arr, low, high);
        QuickSort(arr, low, pivotpos - 1);
        QuickSort(arr, pivotpos + 1, high);
    }
}

// *** 简单选择排序 ***
// 空间复杂度O(1)，时间复杂度O(n^2)
// 不稳定
void SelectSort(int arr[], int len)
{
    int min, temp;
    for (int i = 0; i < len; i++) {
        min = i;
        for (int j = i + 1; j < len; j++) {
            if (arr[min] > arr[j]) {
                min = j;
            }
        }
        if (min != i) {
            temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }
}

// ***** 堆排序 *****
// 什么是堆？大根堆？小根堆？
// 顺序存储的完全二叉树，左孩子：2i，右孩子2i+1，父结点i/2。非叶子结点：i<=n/2
// 大根堆：根>=左、右，堆顶最大
// 小根堆：根<=左、右，堆顶最小

// 建立大根堆：根>=左、右
// 遍历非终端结点：i<=n/2，如果左、右孩子比双亲结点大，则互换
// 换完后需要进行小元素不断下坠过程

// k为根的子树调整为大根堆
void HeadAdjust(int arr[], int k, int len)
{
    arr[0] = arr[k];
    for (int i = k * 2; i <= len; i *= 2) {
        if (i < len && arr[i] < arr[i + 1]) { // 指向最大的孩子
            i++;
        }
        if (arr[0] >= arr[i]) { // 这就是大根堆
            break;
        } else {
            arr[k] = arr[i]; // 子树上来
            k = i;
        }
    }
    arr[k] = arr[0];
}

// 建立大根堆O(n)
void BuildMaxHeap(int arr[], int len)
{
    for (int i = len / 2; i > 0; i--) {
        HeadAdjust(arr, i, len);
    }
}

// 大根堆排序O(nlog2n)
// 不稳定
void HeapSort(int arr[], int len)
{
    BuildMaxHeap(arr, len);
    for (int i = len; i > 1; i--) {
        int temp = arr[i];
        arr[i] = arr[1];
        arr[1] = temp;
        HeadAdjust(arr, 1, i - 1);
    }
}

// 堆的插入删除

// *** 归并排序 ***
// 2个有序序列合并为1个有序序列
// 2路归并/4路归并/m路归并每次需要对比m-1次
// 归并排序：多次2路归并
// 时间O(nlog2n)空间O(n)
// 稳定
// arr[low...mid]和arr[mid+1...high]各自有序，将其归并
int *brr = (int*)malloc(sizeof(int) * 100);
void Merge(int arr[], int low, int mid, int high)
{
    int i, j, k;
    for (i = low; i <= high; i++) {
        brr[i] = arr[i];
    }
    i = low;
    j = mid + 1;
    k = low;
    while (i <= mid && j <= high) {
        if (brr[i] <= brr[j]) { // <= 维持了排序稳定性
            arr[k++] = brr[i++];
        } else {
            arr[k++] = brr[j++];
        }
    }
    while (i <= mid) {
        arr[k++] = brr[i++];
    }
    while (j <= high) {
        arr[k++] = brr[j++];
    }
}

void MergeSort(int arr[], int low, int high)
{
    if (low < high) {
        int mid = (low + high) / 2; // 从中间划分
        MergeSort(arr, low, mid);
        MergeSort(arr, mid+1, high);
        Merge(arr, low, mid, high);
    }
}

// *** 基数排序 ***
// 分配，回收，手动^_^
// 每一位都是0～9，定义10个队列
// 个位依次入队，从大到小出队，十位依次入队...
// 需要r个辅助队列，空间复杂度O(r) 时间复杂度O(n+r)
// 稳定的 基你太稳
// 生日排序：1991 ~ 2005, 01 ~ 12, 01 ~ 31 权重年 > 月 > 日


// **** 外部排序 ****
// 时间开销=读写外存+内部排序+内部归并
// 数据交换：磁盘中以磁盘块为单位存储数据，内存中缓冲区大小 = 磁盘块的大小
// 在内存中处理完数据后，将一块大小的数据写入磁盘块中，数据交换完毕
// 外部排序：没法一次性把磁盘中的数据全部读入内存，思想基于归并排序
// 最小申请3块和磁盘块一样大的缓冲区（2个输入缓冲区，1个输出缓冲区），就可以对任意大小的数据进行排序
// 初始化归并段：读入2块数据，在内存中排好序后，把输入缓冲区1的内容放到输出缓冲区，写入磁盘，再把输入缓冲区2中的内容放到输出缓冲区，写入磁盘
// 磁盘中2个磁盘块大小的归并段完成。重复该过程，可以获得8个初始的归并段，我们可以利用这8个归并段进行归并排序。
// 这个过程进行了16次读和写操作 = 32次读写操作
// 第一趟归并排序：归并段1和归并段2最小的磁盘块读入输入缓冲区，把最小的数字依次放入输出缓冲区，直到输出缓冲区满。
// 把输出缓冲区的数据写入磁盘的第一个位置，***若输入缓冲区为空，应该立即补充***。
// 重复该过程，把2个归并段归并为1个归并段，可以获得4个归并段
// 第二趟归并排序：和第一趟归并是一样的
// 第三趟归并排序：磁盘中16块数据排序完毕。一共进行了3躺，读写次数：32 + 32 * 3 = 128次
// 2路归并的归并树为2叉树，4路归并的归并树为4叉树...n路归并的归并树为n叉树
// 采用4路归并，内存中有4个输入缓冲区，1个输出缓冲区
// 初始化归并段：读入2个数据块，放到输入缓冲区中进行内部排序。把输入缓冲区1的数据放入输出缓冲区，写入磁盘，
// 输入缓冲区2中的数据输入缓冲区，写入磁盘，获得8个初始化归并段
// 第一趟归并排序：读入4个归并段较小的数据块，分别放入4个输入缓冲区，依次把最小的数字放入输出缓冲区中，直到输出缓冲区满
// ***输入缓冲区为空，应该立即补充***
// 获得2个归并段
// 第二趟排序：进行一次2路归并即可完成外部排序
// 读写磁盘次数 = 32 + 32 * 2 = 96次
// 所以采用多路归并，可以减少趟数,初始化归并段r，k路归并的归并趟数 = (h-1) = s = logk(r)向上取整
// 并不是k越大越好：1 需要k个输入缓冲区，增加了内存开销 2 找到最小的数字需要比较k-1次，内部排序时间增加 败者树解决
// r越少越好 r = n / k 置换选择排序解决

// *** 败者树 ***
// s = logk(r)向上取整
// k越大，找到最小元素，每一次比较k-1次，增加排序时间；内存增加；
// 什么失败者树？《天下第一武道大会》
// 8个参赛者需要进行7次比拼。败者树可以视为一颗完全二叉树，非叶子结点代表失败者，记录的值为归并段序号
// 如果冠军跑了，则让新选手从冠军位置开始往上比较
// 使用败者树，k路归并每次只需要对比 log2(k)向上取整次
// 掌握手算方法即可

// *** 置换选择排序 ***
// s = logk(r)向上取整
// r越小越好，但是归并段r越小，就需要越大的内存
// n是磁盘块，l是输入缓冲区大小，r = n / l向上取整 (8 = 16 / 2)
// 土办法：增加输入缓冲区大小
// 新办法：置换选择排序
// 假设内存工作区只能包含3个记录，外面的文件有24个。土办法r = 24 / 3 = 8个归并段
// 读入3个记录放入工作区中，把最小的文件放入归并段，并且minimax=最小文件
// 补充一个文件，如果最小的文件 > minimax，把最小的文件放入归并段中
// 否则如果第二小的文件 > minimax把第二小的文件放入归并段中
// 如果第二小的文件不满足，则比较第三小的文件
// 如果都小于minimax，则新起一个归并段，把最小的文件放入新的归并段中，并且minimax=最小文件
// 获得长短不一的归并段

// *** 最佳归并树 ***
// 置换选择排序获得长短不一的归并段
// 树的带权路径长度WPL = 读磁盘次数 = 写磁盘次数
// 如何获得最短带权路径长度呢？哈夫曼树！
// 多路归并的情况：构造多路哈夫曼树
// 选择k个权值最小的结点进行合并。合并前需要用权值为0的虚拟结点进行补充，满足每次都是k路归并
// 结点数量 = 严格k叉归并树叶子结点数
// n0+nk=n;knk=n-1
// n0+nk=knk+1;n0-1=nk(1-k);nk=(n0-1)/(k-1)应该是整数
#endif /* sort_hpp */
